package algorithm.leetcode.I1to100;

//
// a11  a12  a13 ... a1n-1 a1n        an1  an-11  an-21 ... a21 a11
// a21  a22  a23 ... a2n-1 a2n   ->   an2  an-12  an-22 ... a22 a12
//           ......                            ......
// an1  an2  an3 ... ann-1 ann        ann  an-1n  an-2n ... a2n a1n
//
// 原来的第k列逆序之后放到新的第k行
// a(i,k) = a*(k, n-1-i) (索引从0开始到n-1)
//
// 题意需要常数空间,故只能原地交换
// 思路: 由外环到内环一环一环逐个交换
//
// *  a  * ... *  *      *  a  * ... *  *      *  a  * ... *  *      *  a  * ... *  *      *  d  * ... *  *
// *  *  * ... *  b  =>  *  *  * ... *  a  =>  *  *  * ... *  a  =>  *  *  * ... *  a  =>  *  *  * ... *  a
//         ...                   ...                   ...                   ...                   ...
// d  *  * ... *  *      d  *  * ... *  *      d  *  * ... *  *      c  *  * ... *  *      c  *  * ... *  *
// *  *  * ... c  *      *  *  * ... c  *      *  *  * ... b  *      *  *  * ... b  *      *  *  * ... b  *
//       开始                交换a,备份b             交换b,备份c            交换c,备份d              交换d
//
// tricky的地方在于几个索引

import java.util.Arrays;

public class Q48 {

    public void rotate(int[][] matrix) {
        int circle = (matrix.length+1)>>1;
        int timesPerCircle = matrix.length-1;

        for (int i = 0; i < circle; i++) {
            for (int j = 0; j < timesPerCircle; j++) {
                int[] array = new int[]{i, i+j, matrix[i][i+j]};
                for (int k = 0; k < 4; k++) {
                    rotateHelper(array, matrix);
                }
            }
            timesPerCircle -= 2;
        }

    }

    private void rotateHelper(int[] array, int[][] matrix) {
        // 先计算待替换的元素位置
        int newRow = array[1];
        int newCol = matrix.length-1-array[0];
        // 备份新元素
        int temp = matrix[newRow][newCol];
        // 交换元素
        matrix[newRow][newCol] = array[2];
        // 更新数组
        array[0] = newRow;
        array[1] = newCol;
        array[2] = temp;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3};
        int[] b = {4,5,6};
        int[] c = {7,8,9};
        int[][] aa = new int[][]{a, b,c};
        Q48 q48 = new Q48();
        q48.rotate(aa);
        for (int[] ints : aa) {
            System.out.println(Arrays.toString(ints));
        }
    }
}
